// 2025/3/18
// https://leetcode.cn/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=top-100-liked
// 实现trie(前缀树)

class Trie {
    struct TreeNode{
        char ch;
        TreeNode* child;
        TreeNode* bro;
        bool isWord;

        TreeNode(char _ch)
            :ch(_ch)
            , child(nullptr)
            , bro(nullptr)
            , isWord(false)
        {}
    };
public:
    Trie()
        :root(new TreeNode('0')) 
    {}
    
    void insert(string word) {
        int n = word.size();
        TreeNode* cur = root;
        for(int i = 0; i < n; i++)
        {
            while(cur->bro)
            {
                if(cur->ch == word[i])
                {
                    break;
                }
                cur = cur->bro;
            }

            if(cur->ch == word[i])
                cur = cur->child;
            else
            {
                cur->bro = new TreeNode(word[i]);
                cur->bro->child = new TreeNode('0');
                cur = cur->bro->child;
            }
        }
        cur->isWord = true;
    }
    
    bool search(string word) {
        int n = word.size();
        TreeNode* cur = root;
        for(int i = 0; i < n; i++)
        {
            while(cur->bro)
            {
                if(cur->ch == word[i])
                {
                    break;
                }
                cur = cur->bro;
            }

            if(cur->ch == word[i])
                cur = cur->child;
            else
                return false;
        }
        return cur->isWord;
    }
    
    bool startsWith(string prefix) {
        int n = prefix.size();
        TreeNode* cur = root;
        for(int i = 0; i < n; i++)
        {
            while(cur->bro)
            {
                if(cur->ch == prefix[i])
                {
                    break;
                }
                cur = cur->bro;
            }

            if(cur->ch == prefix[i])
                cur = cur->child;
            else
                return false;
        }
        return true;
    }

    TreeNode* root;
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */